Missing ranges

Time: O(N); Space: O(1); medium

Given a sorted integer array where the range of elements are [lower, upper] inclusive, return its missing ranges.

Example:

Input: nums = [0, 1, 3, 50, 75], lower = 0, upper = 99

Output: [“2”, “4->49”, “51->74”, “76->99”]

class Solution1(object):
    def findMissingRanges(self, nums, lower, upper):
        """
        :type nums: List[int]
        :type lower: int
        :type upper: int
        :rtype: List[str]
        """
        def getRange(lower, upper):
            if lower == upper:
                return "{}".format(lower)
            else:
                return "{}->{}".format(lower, upper)
        ranges = []
        pre = lower - 1

        for i in range(len(nums) + 1):
            if i == len(nums):
                cur = upper + 1
            else:
                cur = nums[i]
            if cur - pre >= 2:
                ranges.append(getRange(pre + 1, cur - 1))

            pre = cur

        return ranges

s = Solution1()
nums = [0, 1, 3, 50, 75]
lower = 0
upper = 99
assert s.findMissingRanges(nums, lower, upper) == ['2', '4->49', '51->74', '76->99']

See also:

https://leetcode.com/problems/missing-ranges

https://www.lintcode.com/problem/missing-ranges